package gold.digger;

import gold.contest.LC5995;
import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC2157 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        /**
         * Created by fanzhenyu02 on 2020/6/27.
         * Union Find 算法实现
         */
        public class UF {
            // 连通分量个数
            private int count;
            // 存储一棵树
            private int[] parent;
            // 记录树的“重量”
            private int[] size;

            public UF(int n) {
                this.count = n;
                parent = new int[n];
                size = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                    size[i] = 1;
                }
            }

            /* 将 p 和 q 连接 */
            public void union(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                if (rootP == rootQ)
                    return;

                // 小树接到大树下面，较平衡
                if (size[rootP] > size[rootQ]) {
                    parent[rootQ] = rootP;
                    size[rootP] += size[rootQ];
                } else {
                    parent[rootP] = rootQ;
                    size[rootQ] += size[rootP];
                }
                count--;
            }

            /* 判断 p 和 q 是否连通 */
            public boolean connected(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                return rootP == rootQ;
            }

            private int find(int x) {
                while (parent[x] != x) {
                    // 进行路径压缩
                    parent[x] = parent[parent[x]];
                    x = parent[x];
                }
                return x;
            }

            /* 返回图中有多少个连通分量 */
            public int count() {
                return count;
            }

            /* 返回图中联通集合 */
            public Map<Integer, List<Integer>> outputAggregateSet(int n) {
                Map<Integer, List<Integer>> aggregateMap = new HashMap<>();

                // 共有n个集合
                for (int i = 0; i < n; i++) {
                    int parentId = find(i);
                    if (!aggregateMap.containsKey(parentId)) aggregateMap.put(parentId, new ArrayList<>());
                    aggregateMap.get(parentId).add(i);
                }

                System.out.println(aggregateMap.toString());
                return aggregateMap;
            }
        }

        public int[] groupStrings(String[] words) {
            UF uf = new UF(words.length);
            Map<Integer, List<Integer>> idxMap = new HashMap<>();

            for (int i = 0; i < words.length; i++) {
                int curWord = strToInt(words[i]);
                if (!idxMap.containsKey(curWord)) idxMap.put(curWord, new ArrayList<>());
                idxMap.get(curWord).add(i);
            }

            // 往 s1 的字母集合中添加一个字母。
            // 从 s1 的字母集合中删去一个字母。
            // 将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）
            for (int i = 0; i < words.length; i++) {
                // 1. 在j删除
                for (int j = 0; j < words[i].length(); j++) {
                    String curChange = words[i].substring(0, j) + words[i].substring(j + 1, words[i].length());
                    int curChangeWord = strToInt(curChange);
                    if (idxMap.containsKey(curChangeWord)) {
                        joinConnection(idxMap.get(curChangeWord), uf, i);
                    }
                }

                for (char ch = 'a'; ch <= 'z'; ch++) {
                    // 2. 添加 ch
                    for (int j = 0; j < words[i].length(); j++) {
                        String curChange = words[i].substring(0, j) + ch + words[i].substring(j, words[i].length());
                        int curChangeWord = strToInt(curChange);
                        if (idxMap.containsKey(curChangeWord)) {
                            joinConnection(idxMap.get(curChangeWord), uf, i);
                        }
                    }
                    if (idxMap.containsKey(strToInt(words[i] + ch))) {
                        joinConnection(idxMap.get(strToInt(words[i] + ch)), uf, i);
                    }

                    // 3. 替换 ch
                    for (int j = 0; j < words[i].length(); j++) {
                        String curChange = words[i].substring(0, j) + ch + words[i].substring(j + 1, words[i].length());
                        int curChangeWord = strToInt(curChange);
                        if (idxMap.containsKey(curChangeWord)) {
                            joinConnection(idxMap.get(curChangeWord), uf, i);
                        }
                    }
                }
            }

            int[] ans = new int[2];
            ans[0] = uf.count;
            int maxCnt = 0;
            for (int wei : uf.size) {
                maxCnt = Math.max(maxCnt, wei);
            }
            ans[1] = maxCnt;
            return ans;
        }

        public int strToInt(String str) {
            int strInt = 0;
            for (int i = 0; i < str.length(); i++) {
                int curBit = 1 << (str.charAt(i) - 'a');
                strInt |= curBit;
            }

            return strInt;
        }

        public void joinConnection(List<Integer> idxList, UF uf, int curIdx) {
            if (null == idxList || idxList.size() <= 0) return;
            for (Integer target : idxList) {
                uf.union(curIdx, target);
            }
        }
    }

    class Solution_Other {

        class UnionFind {
            public int[] parent;
            public int[] size;

            UnionFind() {
            }

            UnionFind(int n) {
                parent = new int[n];
                size = new int[n];
                Arrays.fill(parent, -1);
            }

            public int Find(int x) {
                if (parent[x] != x) {
                    parent[x] = Find(parent[x]);
                }
                return parent[x];
            }

            public boolean Union(int x, int y) {
                int root_x = Find(x);
                int root_y = Find(y);
                if (root_x == root_y) {
                    return false;
                }
                if (size[root_x] > size[root_y]) {
                    int tmp = root_x;
                    root_x = root_y;
                    root_y = tmp;
                }
                parent[root_x] = root_y;
                size[root_y] += size[root_x];
                return true;
            }

            public boolean connected(int x, int y) {
                return Find(x) == Find(y);
            }
        }

        public int[] groupStrings(String[] words) {
            int n = words.length;

            UnionFind UF = new UnionFind(n);

            Map<Long, Integer> word_ID = new HashMap<>();
            Map<Long, Integer> word_cnt = new HashMap<>();

            for (int i = 0; i < n; i++) {
                String word = words[i];
                long state = 0L;
                for (int j = 0; j < word.length(); j++) {
                    state |= (1 << (word.charAt(j) - 'a'));
                }
                word_ID.put(state, i);
                word_cnt.put(state, word_cnt.getOrDefault(state, 0) + 1);
            }

            for (Map.Entry<Long, Integer> entry : word_cnt.entrySet()) {
                Long state = entry.getKey();
                int cnt = entry.getValue();
                int ID = word_ID.get(state);
                UF.parent[ID] = ID;
                UF.size[ID] = cnt;
            }

            for (Map.Entry<Long, Integer> entry : word_cnt.entrySet()) {
                Long state = entry.getKey();
                int cnt = entry.getValue();
                int ID = word_ID.get(state);

                for (int x = 0; x < 26; x++) {
                    if (((state >> x) & 1) == 1) {
                        //-------- 删除
                        long nxt_state = state ^ (1 << x);
                        if (word_ID.containsKey(nxt_state) == true) {
                            int nxt_ID = word_ID.get(nxt_state);
                            UF.Union(ID, nxt_ID);
                        }
                        //-------- 替换
                        for (int y = 0; y < 26; y++) {
                            if (x != y && ((state >> y) & 1) == 0) {
                                nxt_state = state ^ (1 << x);
                                nxt_state |= (1 << y);
                                if (word_ID.containsKey(nxt_state) == true) {
                                    int nxt_ID = word_ID.get(nxt_state);
                                    UF.Union(ID, nxt_ID);
                                }
                            }
                        }

                    }
                }
            }

            int part = 0;
            int max_ = 0;
            for (int x = 0; x < n; x++) {
                if (UF.parent[x] == x) {
                    part++;
                    max_ = Math.max(max_, UF.size[x]);
                }
            }

            return new int[]{part, max_};
        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
//        System.out.println(new Solution().groupStrings(new String[]{"ghnv", "uip", "tenv", "hvepx", "e", "ktc", "byjdt", "ulm", "cae", "ea"}));
//        System.out.println(new Solution_Other().groupStrings(new String[]{"ghnv", "uip", "tenv", "hvepx", "e", "ktc", "byjdt", "ulm", "cae", "ea"}));

        System.out.println(new Solution().groupStrings(new String[]{"scd", "zyrg", "rapkfjtwm", "cipjr", "k", "rgvpxah", "mjtqxewnkzho", "mcoqz", "gui", "vwlqyf", "uhbkjxcstoyqa", "sujfyidcl", "wrvqnzgdt", "bljquvkatcyhxog", "vxn", "dtuneyosqarmp", "oxnilbaezdgf", "gdyrslwke", "yhixq", "prbmyjtz", "gralujz", "uwszfhmoeykg", "wbcpr", "beszfhucayvp", "swixbotnme", "dqas", "nqau", "sopfe", "drixva", "ktmoghupdezq", "kisbhvrofwgea", "xiqucae", "pvuxqbfnw", "gnkqcfw", "kapzbgjf", "hrnxdpgtcevz", "zhajlipq", "umcowilb", "tgfwjvslrizmdu", "hzyjcoqxikdnrep", "simqjzvabopyeku", "cqhfd", "ogstymfhxu", "eghvqmodlnba", "gahrwyu", "eonpsjlaqctwr", "glsqcto", "p", "ndpc", "rdyg", "ewbzinxhc", "fcqkxmiozraw", "nmtzedsjqb", "uscxzoarlg", "rxeiolvyna", "gvwqxodaui", "rdzuk", "culaietk", "r", "swrxanjludpmkf", "jmxruascvwd", "ckvy", "nkzol", "s", "uhiks", "tr", "gv", "swteuzxkfbopcjy", "ctfdrpl", "zu", "bmp", "xjs", "w", "ndzivojktaryxs", "dpsqagjyltrmbi", "rcsfqlwyeo", "dafuchpz", "ibr", "gsqlmxbtcjp", "pagv", "e", "pjzmevulbrd", "c", "khgfi", "biudrvt", "fuqypcmnovx", "ehsqln", "yprnmoxdlvjwh", "uwifb", "tjozhbnqwe", "yqdvlsepc", "kcngidaemzwysjo", "jqxagtnzebil", "rb", "azhyocvmsgxqukd", "bgjxzqadf", "ugvfjlca", "dfl", "vsjxwdym", "rsvmtlufkewqajz", "ailhzw", "cpvg", "yepxkc", "vhb", "ylpjmhnusewizqb", "ors", "gmvizheyjrc", "diwtyncxsfu", "qjagvc", "gzlrk", "ldbofsc", "cdfigzkymquan", "x", "lsaeukt", "dygarwjsufkihl", "xbpgnuyajz", "hfvkndj", "keaotjuxwpyhscf", "xub", "ruxfp", "hmcjfbzyio", "qmtdfaczuhb", "mavcue", "xlrdzpq", "shcazplf", "jxveilys", "gszm", "zcvlkhuojymnpf", "qecjzyrdpshiuto", "grp", "lvawkempjrgzf", "zp", "onzdcwhtvsr", "ug", "avqgcdpyhrkuftb", "ljvb", "jqlrn", "tupiblxjfsqawe", "yutmqsoikna", "hwjzyatmgdlox", "pujisnvwblfogzx", "tsrmbcfkup", "fiegc", "u", "ncyvdajmrgbpt", "ylxanevshiwpz", "msevxb", "ieocyrjbzutxghp", "wyavohec", "ismndupal", "cnkd", "a", "jvfalyoibxsur", "hxjilcty", "nfblvykdmepag", "aqtcwmjxu", "sbtrgc", "atvscrq", "adlmyiotbkzgc", "uwejlbhycron", "htfxdbv", "mxhesqubiz", "jgsxdhvtikmzluo", "zumikwyvrjcgaf", "iuelaowynvbd", "zqb", "wz", "ulwqmj", "netyph", "ncj", "urqpbohcxvgntw", "qlvscipbhra", "btqmkioawy", "z", "lbjitewvk", "md", "oldnmc", "xrgebpsuwjok", "xfcthlkunvmgswa", "qgdbxprlhfsniac", "mdlpniubefto", "ai", "aecdjylxumkp", "alxzebmy", "iqb", "zyqxljutr", "vmrt", "lquhfkncbvimy", "umfwnsqltvec", "zicmlqynsubvft", "ltgqmadswy", "opkh", "ehlmrjsu", "nfswhgkecvpir", "qetjzgolbpyd", "taw", "vgksidnr", "zfemiswy", "j", "yf", "kmputjogyfdxwi", "n", "j", "pktcd", "o", "soxli", "qolpr", "fuyndszgpqlkx", "swikecup", "bakgqryclhomes", "dnbiv", "movirkejdba", "xagfbwlezp", "ltgbayi", "dqugzfoyvk", "sjr", "lxomaptji", "bxiu", "vmne", "oiz", "mixqftjazsvw", "syqklrdeb", "cfmbvaqwtkxone", "khcwqutsd", "vipgkmdfas", "wbmtvzque", "oacdezq", "szblvfhnmcjy", "dwsnye", "gnwlos", "ji", "t", "ciyfnqmtagzpxsr", "s", "c", "ycixabsefnojtdr", "anjbczyexr", "etdqckbawyi", "izkpdmcf", "muzsjklidf", "vuipjchmqnxfg", "xgzpsmafku", "dstir", "fsydqlphaobvzik", "cgekpida", "cvgqdz", "rieafhx", "vanczbhm", "cq", "ufcarsjpzvmx", "amcvbsyjidxfrpk", "xiqbmwelfa", "xmwdlvgknibrya", "s", "idghquonalbvtm", "vz", "w", "webgpjm", "ahyjn", "euakyn", "di", "yejpusr", "l", "nqdvztkcwomjg", "ecpfkwxtoibyrmj", "wxjthlgay", "ebsomavcnd", "jrhvlftkypmqs", "grdbqpm", "ehxlibv", "loajm", "mogzbve", "mvkhoeray", "tq", "aeyot", "jxkemwzyrdvapc", "yvonl", "jmkirxvltnbh", "goqk", "wgsrpy", "qfagn", "ob", "vdywmhleugnfoix", "cngjb", "gwahmforybdtzi", "ztmnyio", "whrom", "bozpsjw", "xfdu", "udwzhcrtne", "hzautfljsder", "wojirpzsu", "mzshjuretkafvgq", "dzosgcfk", "fthegpmczsi", "yxni", "tjiyelnh", "wlboduyktzqg", "mcinrdol", "gijbl", "ksbnlerhm", "f", "eiynpuzb", "hq", "a", "qpbntiug", "cybjonzswehvd", "rwhaugtsnfb", "ajufnltdseqwz", "wpcuqjndxh", "fvwyszxmnebdigl", "dynkjglhi", "ds", "eprcgt", "fpuzatdgs", "zldujohm", "ohmk", "lxvc", "bqzkyljgwafn", "ixksdbjcu", "lncwdqyvhjr", "qwzgrehoi", "dhecoxszm", "lcuf", "q", "ijhprseoaulxty", "bkhiqrtuejxgwzd", "cmknrtvwbdfz", "ofje", "lmhbnwxz", "mytbwzdprqosg", "ldwzoybp", "dsbqyfpneh", "px", "xmlcfuvybktrzp", "vylbmdk", "hcnkvyxql", "us", "j", "xsnawedvpkiuj", "fqzwndlovrti", "vodctnakuy", "qhuijsnvfzlg", "pzijncvlodsruha", "dgxtvbpof", "npljdv", "ilthf", "mloydrjbxqsi", "rpowgshncbmtfkx", "ulgskpdifxbrctn", "hr", "miqkw", "n", "uemlvpkbgdwao", "jfniwr", "otlkhfzpmsiaq", "j", "lnbdehsmiw", "xup", "ilnpadzw", "stjqrhwalo", "pxoihzgfmn", "djrv", "di", "fihmu", "wclqigozdejrmfx", "hgmciyzea", "bcw", "nbxaquho", "mvlqs", "kgdw", "kyefpmw", "jpwed", "xncghwuokfydem", "gxjsmdvlpenh", "tjfblaw", "qgldybvaenip", "gutqakcwjvfmer", "tklvwnms", "hfsbmjxnylueo", "cbjqxlymiphwr", "jtchsnrmezy", "ukgfyoj", "huopyrjmbvnecad", "nlujcytvwgkrbih", "cgjrtdf", "kobsuyvpazqj", "bltzdwjxhafsy", "bsw", "juxnm", "cvnkxughbdrpi", "afb", "cnvogwjyskfd", "olngs", "fbhmcn", "tourfegawhnxcjq", "sfkld", "olbfdzymwnehug", "ibpfsjehuaor", "moskqtzwhxpnar", "id", "afykmx", "xpwm", "diptqlwo", "ktxlhiqcfevpn", "jgukexd", "eqfxsmbaktdy", "dxghqkwty", "vdpylsfzn", "ndlymptz", "owzsbjnfcirake", "nbfqxlkdgsvhre", "ngtqkcwufh", "rwe", "fdwzcs", "drnucygxloakjew", "zpo", "alyd", "bdytmrvlngi", "jqphiur", "e", "oginrfaqwz", "qebiypnxlhk", "gtihbqycdm", "v", "mrcgqa", "lpbv", "jvrz", "puarwftimx", "v", "ykvcsruioe", "mxviwyoedg", "asdj", "tieyugzl", "g", "zaxnqykiltbeump", "xrmpcfhaswulzqy", "egnv", "liuqyz", "guqyidhbj", "dlvgpnmbthwj", "ijgd", "euovxgpaknyri", "gesovtbcyipzna", "dwqokpcb", "hezqpjiucyxt", "yca", "fg", "byrhlfoupqemiv", "jnbalep", "mpvibe", "edcyhaurvqixm", "hxkrzupoel", "loyhvnbijxfmg", "habl", "nihgumqaet", "hjgyacswiklunob", "iwstdqaz", "humeaqgcbdfyv", "otrhfbnxywgmus", "dgapjx", "qiur", "ntdgyp", "mlcyk", "ytlp", "oaip", "bhockfm", "ycnqsadkxl", "tulhe", "gflnyjsbdp", "szgjdukw", "ms", "uwtflszxm", "myk", "pqczosrfxgdm", "ztijeowvdck", "kwb", "skvjflrtzd", "ajtmwi", "kyinsmuflwhajg", "pmqra", "slbtoqgij", "za", "lbwaqzxo", "lwsozavmb", "p", "zrjaetkmwyxlv", "f", "mqtbyriw", "yczwgxqmtind", "qy", "e", "uvmgztpokail", "juoylt", "juircy", "lq", "wzymdixlfub", "wapkmdyrecv", "yjmw", "gcxndemawt", "k", "ezrljxukqiyd", "m", "alx", "emfspwjqyhtodab", "dlhzucvgpw", "pzsfgoweim", "qu", "vplxufamtih", "thkrpljcomif", "ijws", "mcejkbwhqof", "uxskpob", "shbopdagr", "hryqs", "ojb", "kmxpgzayhdl", "et", "nygqm", "elvbzowsnxjgky", "ctzrsqgduniv", "uxchjovqkp", "utyrhvcnkle", "hxagkb", "hklyzp", "qjwdzkir", "zju", "dvhupikcarjmyzt", "w", "nzxbouth", "blvigpfshwemjtq", "xjmcok", "yvfjszghmtwcr", "jaqkbvoxrignz", "jocgbtfrvuze", "ykto", "u", "fveazbyk", "gjtsvwqc", "djink", "ovxaqr", "xksgwdvte", "fenyrjomqtcdhxa", "hl", "mgdfeu", "jbl", "y", "qlhtojukxz", "nbxlrg", "cmyiwjruvpq", "asivteonjgkqwxu", "kn", "owkalbmnyiqgtue", "ucbohldfjepsva", "vz", "xzkfjgrbplmqihc", "vrlgsxcn", "fzvhyprkiamwq", "jtrxocau", "kbjvhtfdgiecyms"}));
        System.out.println(new Solution_Other().groupStrings(new String[]{"scd", "zyrg", "rapkfjtwm", "cipjr", "k", "rgvpxah", "mjtqxewnkzho", "mcoqz", "gui", "vwlqyf", "uhbkjxcstoyqa", "sujfyidcl", "wrvqnzgdt", "bljquvkatcyhxog", "vxn", "dtuneyosqarmp", "oxnilbaezdgf", "gdyrslwke", "yhixq", "prbmyjtz", "gralujz", "uwszfhmoeykg", "wbcpr", "beszfhucayvp", "swixbotnme", "dqas", "nqau", "sopfe", "drixva", "ktmoghupdezq", "kisbhvrofwgea", "xiqucae", "pvuxqbfnw", "gnkqcfw", "kapzbgjf", "hrnxdpgtcevz", "zhajlipq", "umcowilb", "tgfwjvslrizmdu", "hzyjcoqxikdnrep", "simqjzvabopyeku", "cqhfd", "ogstymfhxu", "eghvqmodlnba", "gahrwyu", "eonpsjlaqctwr", "glsqcto", "p", "ndpc", "rdyg", "ewbzinxhc", "fcqkxmiozraw", "nmtzedsjqb", "uscxzoarlg", "rxeiolvyna", "gvwqxodaui", "rdzuk", "culaietk", "r", "swrxanjludpmkf", "jmxruascvwd", "ckvy", "nkzol", "s", "uhiks", "tr", "gv", "swteuzxkfbopcjy", "ctfdrpl", "zu", "bmp", "xjs", "w", "ndzivojktaryxs", "dpsqagjyltrmbi", "rcsfqlwyeo", "dafuchpz", "ibr", "gsqlmxbtcjp", "pagv", "e", "pjzmevulbrd", "c", "khgfi", "biudrvt", "fuqypcmnovx", "ehsqln", "yprnmoxdlvjwh", "uwifb", "tjozhbnqwe", "yqdvlsepc", "kcngidaemzwysjo", "jqxagtnzebil", "rb", "azhyocvmsgxqukd", "bgjxzqadf", "ugvfjlca", "dfl", "vsjxwdym", "rsvmtlufkewqajz", "ailhzw", "cpvg", "yepxkc", "vhb", "ylpjmhnusewizqb", "ors", "gmvizheyjrc", "diwtyncxsfu", "qjagvc", "gzlrk", "ldbofsc", "cdfigzkymquan", "x", "lsaeukt", "dygarwjsufkihl", "xbpgnuyajz", "hfvkndj", "keaotjuxwpyhscf", "xub", "ruxfp", "hmcjfbzyio", "qmtdfaczuhb", "mavcue", "xlrdzpq", "shcazplf", "jxveilys", "gszm", "zcvlkhuojymnpf", "qecjzyrdpshiuto", "grp", "lvawkempjrgzf", "zp", "onzdcwhtvsr", "ug", "avqgcdpyhrkuftb", "ljvb", "jqlrn", "tupiblxjfsqawe", "yutmqsoikna", "hwjzyatmgdlox", "pujisnvwblfogzx", "tsrmbcfkup", "fiegc", "u", "ncyvdajmrgbpt", "ylxanevshiwpz", "msevxb", "ieocyrjbzutxghp", "wyavohec", "ismndupal", "cnkd", "a", "jvfalyoibxsur", "hxjilcty", "nfblvykdmepag", "aqtcwmjxu", "sbtrgc", "atvscrq", "adlmyiotbkzgc", "uwejlbhycron", "htfxdbv", "mxhesqubiz", "jgsxdhvtikmzluo", "zumikwyvrjcgaf", "iuelaowynvbd", "zqb", "wz", "ulwqmj", "netyph", "ncj", "urqpbohcxvgntw", "qlvscipbhra", "btqmkioawy", "z", "lbjitewvk", "md", "oldnmc", "xrgebpsuwjok", "xfcthlkunvmgswa", "qgdbxprlhfsniac", "mdlpniubefto", "ai", "aecdjylxumkp", "alxzebmy", "iqb", "zyqxljutr", "vmrt", "lquhfkncbvimy", "umfwnsqltvec", "zicmlqynsubvft", "ltgqmadswy", "opkh", "ehlmrjsu", "nfswhgkecvpir", "qetjzgolbpyd", "taw", "vgksidnr", "zfemiswy", "j", "yf", "kmputjogyfdxwi", "n", "j", "pktcd", "o", "soxli", "qolpr", "fuyndszgpqlkx", "swikecup", "bakgqryclhomes", "dnbiv", "movirkejdba", "xagfbwlezp", "ltgbayi", "dqugzfoyvk", "sjr", "lxomaptji", "bxiu", "vmne", "oiz", "mixqftjazsvw", "syqklrdeb", "cfmbvaqwtkxone", "khcwqutsd", "vipgkmdfas", "wbmtvzque", "oacdezq", "szblvfhnmcjy", "dwsnye", "gnwlos", "ji", "t", "ciyfnqmtagzpxsr", "s", "c", "ycixabsefnojtdr", "anjbczyexr", "etdqckbawyi", "izkpdmcf", "muzsjklidf", "vuipjchmqnxfg", "xgzpsmafku", "dstir", "fsydqlphaobvzik", "cgekpida", "cvgqdz", "rieafhx", "vanczbhm", "cq", "ufcarsjpzvmx", "amcvbsyjidxfrpk", "xiqbmwelfa", "xmwdlvgknibrya", "s", "idghquonalbvtm", "vz", "w", "webgpjm", "ahyjn", "euakyn", "di", "yejpusr", "l", "nqdvztkcwomjg", "ecpfkwxtoibyrmj", "wxjthlgay", "ebsomavcnd", "jrhvlftkypmqs", "grdbqpm", "ehxlibv", "loajm", "mogzbve", "mvkhoeray", "tq", "aeyot", "jxkemwzyrdvapc", "yvonl", "jmkirxvltnbh", "goqk", "wgsrpy", "qfagn", "ob", "vdywmhleugnfoix", "cngjb", "gwahmforybdtzi", "ztmnyio", "whrom", "bozpsjw", "xfdu", "udwzhcrtne", "hzautfljsder", "wojirpzsu", "mzshjuretkafvgq", "dzosgcfk", "fthegpmczsi", "yxni", "tjiyelnh", "wlboduyktzqg", "mcinrdol", "gijbl", "ksbnlerhm", "f", "eiynpuzb", "hq", "a", "qpbntiug", "cybjonzswehvd", "rwhaugtsnfb", "ajufnltdseqwz", "wpcuqjndxh", "fvwyszxmnebdigl", "dynkjglhi", "ds", "eprcgt", "fpuzatdgs", "zldujohm", "ohmk", "lxvc", "bqzkyljgwafn", "ixksdbjcu", "lncwdqyvhjr", "qwzgrehoi", "dhecoxszm", "lcuf", "q", "ijhprseoaulxty", "bkhiqrtuejxgwzd", "cmknrtvwbdfz", "ofje", "lmhbnwxz", "mytbwzdprqosg", "ldwzoybp", "dsbqyfpneh", "px", "xmlcfuvybktrzp", "vylbmdk", "hcnkvyxql", "us", "j", "xsnawedvpkiuj", "fqzwndlovrti", "vodctnakuy", "qhuijsnvfzlg", "pzijncvlodsruha", "dgxtvbpof", "npljdv", "ilthf", "mloydrjbxqsi", "rpowgshncbmtfkx", "ulgskpdifxbrctn", "hr", "miqkw", "n", "uemlvpkbgdwao", "jfniwr", "otlkhfzpmsiaq", "j", "lnbdehsmiw", "xup", "ilnpadzw", "stjqrhwalo", "pxoihzgfmn", "djrv", "di", "fihmu", "wclqigozdejrmfx", "hgmciyzea", "bcw", "nbxaquho", "mvlqs", "kgdw", "kyefpmw", "jpwed", "xncghwuokfydem", "gxjsmdvlpenh", "tjfblaw", "qgldybvaenip", "gutqakcwjvfmer", "tklvwnms", "hfsbmjxnylueo", "cbjqxlymiphwr", "jtchsnrmezy", "ukgfyoj", "huopyrjmbvnecad", "nlujcytvwgkrbih", "cgjrtdf", "kobsuyvpazqj", "bltzdwjxhafsy", "bsw", "juxnm", "cvnkxughbdrpi", "afb", "cnvogwjyskfd", "olngs", "fbhmcn", "tourfegawhnxcjq", "sfkld", "olbfdzymwnehug", "ibpfsjehuaor", "moskqtzwhxpnar", "id", "afykmx", "xpwm", "diptqlwo", "ktxlhiqcfevpn", "jgukexd", "eqfxsmbaktdy", "dxghqkwty", "vdpylsfzn", "ndlymptz", "owzsbjnfcirake", "nbfqxlkdgsvhre", "ngtqkcwufh", "rwe", "fdwzcs", "drnucygxloakjew", "zpo", "alyd", "bdytmrvlngi", "jqphiur", "e", "oginrfaqwz", "qebiypnxlhk", "gtihbqycdm", "v", "mrcgqa", "lpbv", "jvrz", "puarwftimx", "v", "ykvcsruioe", "mxviwyoedg", "asdj", "tieyugzl", "g", "zaxnqykiltbeump", "xrmpcfhaswulzqy", "egnv", "liuqyz", "guqyidhbj", "dlvgpnmbthwj", "ijgd", "euovxgpaknyri", "gesovtbcyipzna", "dwqokpcb", "hezqpjiucyxt", "yca", "fg", "byrhlfoupqemiv", "jnbalep", "mpvibe", "edcyhaurvqixm", "hxkrzupoel", "loyhvnbijxfmg", "habl", "nihgumqaet", "hjgyacswiklunob", "iwstdqaz", "humeaqgcbdfyv", "otrhfbnxywgmus", "dgapjx", "qiur", "ntdgyp", "mlcyk", "ytlp", "oaip", "bhockfm", "ycnqsadkxl", "tulhe", "gflnyjsbdp", "szgjdukw", "ms", "uwtflszxm", "myk", "pqczosrfxgdm", "ztijeowvdck", "kwb", "skvjflrtzd", "ajtmwi", "kyinsmuflwhajg", "pmqra", "slbtoqgij", "za", "lbwaqzxo", "lwsozavmb", "p", "zrjaetkmwyxlv", "f", "mqtbyriw", "yczwgxqmtind", "qy", "e", "uvmgztpokail", "juoylt", "juircy", "lq", "wzymdixlfub", "wapkmdyrecv", "yjmw", "gcxndemawt", "k", "ezrljxukqiyd", "m", "alx", "emfspwjqyhtodab", "dlhzucvgpw", "pzsfgoweim", "qu", "vplxufamtih", "thkrpljcomif", "ijws", "mcejkbwhqof", "uxskpob", "shbopdagr", "hryqs", "ojb", "kmxpgzayhdl", "et", "nygqm", "elvbzowsnxjgky", "ctzrsqgduniv", "uxchjovqkp", "utyrhvcnkle", "hxagkb", "hklyzp", "qjwdzkir", "zju", "dvhupikcarjmyzt", "w", "nzxbouth", "blvigpfshwemjtq", "xjmcok", "yvfjszghmtwcr", "jaqkbvoxrignz", "jocgbtfrvuze", "ykto", "u", "fveazbyk", "gjtsvwqc", "djink", "ovxaqr", "xksgwdvte", "fenyrjomqtcdhxa", "hl", "mgdfeu", "jbl", "y", "qlhtojukxz", "nbxlrg", "cmyiwjruvpq", "asivteonjgkqwxu", "kn", "owkalbmnyiqgtue", "ucbohldfjepsva", "vz", "xzkfjgrbplmqihc", "vrlgsxcn", "fzvhyprkiamwq", "jtrxocau", "kbjvhtfdgiecyms"}));
    }

    public static void main(String[] args) throws Exception {
        LC2157 an = new LC2157();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
